package com.yinxin.wudasuanfa.huaweiod.treeSearch;


import java.util.LinkedList;

public class TreeTest {

    public TreeNode getTargetTree() {
        // 叶子节点
        TreeNode G = new TreeNode("G");
        TreeNode D = new TreeNode("D");
        TreeNode E = new TreeNode("E", G, null);
        TreeNode B = new TreeNode("B", D, E);
        TreeNode H = new TreeNode("H");
        TreeNode I = new TreeNode("I");
        TreeNode F = new TreeNode("F", H, I);
        TreeNode C = new TreeNode("C", null, F);
        // 构造根节点
        TreeNode root = new TreeNode("A", B, C);
        return root;
    }

    /**
     * 前序遍历 先根节点->左子树->右子树；
     */
    public void preOrderVisitTreeNode(TreeNode node) {
        if (null != node) {
            System.out.print(node.value);
            if (null != node.getLeftChildren()) {
                preOrderVisitTreeNode(node.getLeftChildren());
            }
            if (null != node.getRightChildren()) {
                preOrderVisitTreeNode(node.getRightChildren());
            }
        }
    }

    /**
     *  中序遍历 先左子树->根节点->右子树；
     */
    public void inorderVisitTreeNode(TreeNode node) {
        if (null != node) {
            if (null != node.getLeftChildren()) {
                inorderVisitTreeNode(node.getLeftChildren());
            }
            System.out.print(node.value);
            if (null != node.getRightChildren()) {
                inorderVisitTreeNode(node.getRightChildren());
            }
        }
    }

    /**
     *  后序遍历 先左子树->右子树->根节点；
     */
    public void postOrderVisitTreeNode(TreeNode node) {
        if (null != node) {
            if (null != node.getLeftChildren()) {
                postOrderVisitTreeNode(node.getLeftChildren());
            }
            if (null != node.getRightChildren()) {
                postOrderVisitTreeNode(node.getRightChildren());
            }
            System.out.print(node.value);
        }
    }

    /**
     * 层次遍历
     */
    public void levelOrderVisitTreeNode(TreeNode node) {
        if (null != node) {
            LinkedList<TreeNode> list = new LinkedList<>();
            list.add(node);
            TreeNode currentNode;
            while (!list.isEmpty()) {
                currentNode = list.poll();
                System.out.print(currentNode.value);
                if (null != currentNode.getLeftChildren()) {
                    list.add(currentNode.getLeftChildren());
                }
                if (null != currentNode.getRightChildren()) {
                    list.add(currentNode.getRightChildren());
                }
            }
        }
    }

    public static void main(String[] args) {
        TreeTest treeSearch = new TreeTest();
        TreeNode tree = treeSearch.getTargetTree();
        System.out.print("前序遍历:");
        treeSearch.preOrderVisitTreeNode(tree);
        System.out.println("");
        System.out.print("中序遍历:");
        treeSearch.inorderVisitTreeNode(tree);
        System.out.println("");
        System.out.print("后序遍历:");
        treeSearch.postOrderVisitTreeNode(tree);
        System.out.println("");
        System.out.print("层次遍历:");
        treeSearch.levelOrderVisitTreeNode(tree);
    }
}